The present invention relates to the field of information visualization and in particular to the display of representations of linked information based on user interest.
Many applications of computers to practical problems involve the display of representations of linked information such as hierarchical data. Linked information refers to information that has some logical or organizational relationship. Examples are organization charts, computer programs, Web sites, filing systems, or biological taxonomies. These data structures are often much larger than will conveniently fit on the screen of a computer display monitor so that information can be easily extracted. But finding a way of presenting these structures to users such that (1) they can find elements in the structure quickly and (2) they can understand the relationship of an element to its surrounding context is an important enabler to many uses of such data.
One example is in the area of linked hierarchical data. Linked hierarchical data is often displayed in a tree structure. Several types of methods have been used to display such tree structures:
(1) Uniform layout of trees. Trees can be laid out uniformly. The number of nodes at the leaves of all the subtrees is computed and multiplied by an amount of space per node plus spacing between nodes and between subtrees. Then the nodes are scaled so that this fits across the display. This method works for small trees, but any attempt to portray a tree structure of moderate size, say 600 nodes, scaled to the width of a display will have the approximate appearance of a horizontal line, since the width increases exponentially while the height increases only linearly.
(2) Compressed layout of trees. The space required for the tree can be opportunistically compressed by sliding portions of deeper subtrees underneath shallow subtrees. If the tree has uniform depth, this is of no help. If the depth is non-uniform, more nodes can be accommodated in the same space, but this technique is only a limited improvement and cannot handle very large trees.
(3) Treemaps. Treemaps are described by Johnson, B. and Shneiderman, B. in the publication entitled xe2x80x9cTreemaps: A space-filing approach to the visualization of hierarchical information structuresxe2x80x9d, Proceedings of IEEE Information Visualization ""91, 275-282. Treemaps is a technique in which lower subtrees are contained within higher nodes of the tree. A space is divided, say vertically, into a number of sections equal to the number of branches. Each section is then divided horizontally according to the number of branching at the next level down in the tree. The next level is then divided vertically again and so on alternating between vertical and horizontal definition of the space until it is too small to divide. Since creating a tree in this way does not allow any room for the content of nodes, the technique can be modified so that each division has extra space to be devoted to the node contents. This technique stays within predetermined space bounds, but as nodes become smaller and smaller they no longer have room for content (except for maybe a uniform color), the aspect ratios of the nodes vary widely, obscuring simple relationships.
(4) Techniques of variable manual expansion. Some techniques allow the user to choose which nodes are displayed. In this way, there need not be space for all nodes at the same time and those visible are ones more interesting to the user. One such technique was introduced in by Engelbart, D. C. and English, W. K., xe2x80x9cA Research Center for Augmenting Human Intellectxe2x80x9d, AFIPS Conference Proceedings of the 1968 Fall Joint Computer Conference, San Francisco, Calif., December 1968, Vol. 33, pp. 395-410 (AUGMENT,3954,). Republished in Computer Supported Cooperative Work: A Book of Readings, Irene Greif [Editor], Morgan Kaufmann Publishers, Inc., San Mateo, Calif., 1988, pp. 81-105. The user indicates the higher and lower level numbers of the tree to be expanded. This technique allows the user to look horizontally across a tree structure. For example, a user might look at all the procedure call and variable declarations in a program, while suppressing the code itself, which resides at lower levels in the tree. The limitation of this technique is that there is no guarantee the tree will all fit on the display in any of these views and the user cannot expand one part of the tree, but not another. So the technique is usually paired with scrolling.
Another example of such a technique is used in the user interface of the Apple Hierarchical Filing System used on computer systems available from Apple Computer, Inc. of Cupertino Calif. Each level in the tree can be expanded individually by clicking on a small triangle to the left of the level. Thus the user can expand portions of the tree that are to be compared on the screen, while keeping other portions of the tree compressed by eliding nodes below the compressed subtree root. But this technique also needs to be paired with scrolling and considerable manual manipulation must be performed by the user to constantly adjust views.
(5) Fish-eye Views. Fish-eye views were described by Furnas, G. W. (1981/1999), in the publication xe2x80x9cThe FISHEYE View: A new look at structured filesxe2x80x9d, reprinted in Card, S. K., Mackinlay, J. D.; and Shneiderman, B. (eds.) (1999), Information Visualization: Using Vision to Think. San Francisco: Morgan-Kaufmann. Fish-eye views describes a class of techniques in which nodes are displayed or elided according to the user""s computed degree-of-interest (DOI) in them. The estimated
DOI of a node=Intrinsic Importance+Distance from a focus node.
The Intrinsic Importance of a node is its distance from the root and the Distance of a node is the number of nodes that must be traversed by following parent and child links from the node of interest until reaching the subject node. All those nodes whose DOI lies below a certain threshold are not displayed. If the user indicates interest in some node, say by selecting it, this calculation is performed and the display elides those nodes below the threshold. In this way, the display of the tree follows the user""s changing interest. The problem with this technique is that there is no guarantee the displayed trees will fit in any display bounds, thus wasting useful information space. The technique is especially problematic when there are a large number of sibling nodes in the tree.
(6) Focus+Context Displays. Focus+context displays are variants of fish-eye views that use various sorts of techniques to devote more space or detail of the display to some areas of interest, compressing other parts of the displayed structure to mainly support the context of the focus elements and showing the user where to select to navigate to a new position in the structure. One example of a focus+context hierarchical structure is cone-trees (see Robertson, G. G., Mackinlay, J. D. and Card, S. K. (1991). Cone trees: Animated 3D visualizations of hierarchical information. Proceedings of CHI ""91. ACM Conference on Human Factors in Computing Systems New York, 198-194.). Cone-trees arrange the nodes in a 3-D tree. Selecting a node rotates a branch of the cone-tree, bringing related nodes into the foreground while sending other nodes into the background. This technique uses natural perspective to achieve some of the effect of Furnas""s fish-eye views. Furnas"" fish-eye view technique can be combined with cone-trees, thus allowing the display of larger trees. Because this is a 3-D display, some of the nodes occlude each other.
(7) Hyperbolic Trees. In hyperbolic trees the space itself is stretched according to a hyperbolic projection (see Lamping, J. and Rao, R. (1994), xe2x80x9cLaying out and visualizing large trees using a hyperbolic spacexe2x80x9d, Proceedings of UIST ""94, ACM Symposium on User Interface Software and Technology, 13-14).
An implementation of a hyperbolic tree structure visualization is available from InXight Software, Inc. of Santa Clara, Calif.). Selecting a node moves it to the center (or side) of the display. Nodes further out are smaller and closer to each other. The display stays within fixed boundaries. But only a limited number of links out from the focus node can be seen. Moreover, it is more complicated to model complex user""s DOI.
Despite such methods and techniques there remains a need to effectively display and extract useful information from large bodies of linked data.
The present invention provides for user browsing of large collections of linked information on a computer based display. A visualization is created which presents a representation of the complete collection of information on the display. The visualization fits completely within a fixed area of the computer based display, negating the need to scroll information into or out of the display area. The visualization is based on identified focus nodes and through calculation of a Degree of Interest (DOI) for each of the nodes in the structure. Layout and presentation of the visualization structure is based on the DOI values in combination with considerations of available display space. A user may dynamically manipulate views of the structure by selecting one or more focus nodes, thus causing a recalculation of the degree of interest.
The present invention may be used to display information units comprised of data items that are static, dynamic or a combination of both static and dynamic. An example of information units having static data items would be the nodes in an organization chart. An example of an information unit having dynamic data would be the representation of a web site wherein an information unit represents a web page within the site and includes a dynamic data item representing the number of xe2x80x9chitsxe2x80x9d that corresponding page is encountering over some period of time.
The method of the present invention is for displaying a representation of an entire collection of linked information using a visualization technique in a display area, said linked information comprised of a plurality of nodes each having one or more links to other of said plurality of nodes, the method generally comprising the steps of: identifying one or more focus nodes from said plurality of nodes; generating a degree of interest (DOI) value for each of said plurality of nodes, said degree of interest value relative to said one or more focus nodes and corresponding to a manner in which said node will be displayed; laying out said plurality of nodes according to said visualization technique so that said representation is displayed completely in said display area; displaying said linked information based on said layout of plurality of nodes in said display area